/*
https://leetcode.cn/problems/tree-of-coprimes/description/
1766. 互质树
方钊堉 2024.11.6
dfs
*/

const int MAX = 51;
vector<int> coprime[MAX];

// 预处理：coprime[i] 保存 [1, MAX) 中与 i 互质的所有元素
auto init = [] {
    for (int i = 1; i < MAX; i++) {
        for (int j = 1; j < MAX; j++) {
            if (std::gcd(i, j) == 1) {
                coprime[i].push_back(j);
            }
        }
    }
    return 0;
}();

class Solution {
    vector<vector<int>> graph; // 图的邻接表表示
    vector<int> result; // 存储最终结果
    pair<int, int> valueDepthId[MAX]; // 包含深度和节点编号

    // 深度优先搜索函数
    void dfs(int currentNode, int parent, int currentDepth, const vector<int>& values) {
        int currentValue = values[currentNode]; // 当前节点的值
        int maxDepth = 0; // 当前最大深度
        int maxDepthNodeId = -1; // 当前最大深度对应的节点编号

        // 查找与 currentValue 互质的数中，深度最大的节点编号
        for (int j : coprime[currentValue]) {
            auto [depth, nodeId] = valueDepthId[j];
            if (depth > maxDepth) {
                maxDepth = depth;
                maxDepthNodeId = nodeId;
            }
        }

        result[currentNode] = maxDepthNodeId; // 更新结果

        auto temp = valueDepthId[currentValue]; // 保存当前状态，用于恢复
        valueDepthId[currentValue] = {currentDepth, currentNode}; // 更新当前节点的深度和编号

        // 继续搜索子节点
        for (int child : graph[currentNode]) {
            if (child != parent) {
                dfs(child, currentNode, currentDepth + 1, values);
            }
        }

        valueDepthId[currentValue] = temp; // 恢复现场
    }

public:
    vector<int> getCoprimes(const vector<int>& values, const vector<vector<int>>& edges) {
        int n = values.size();
        graph.resize(n);
        for (const auto& edge : edges) {
            int u = edge[0], v = edge[1];
            graph[u].push_back(v);
            graph[v].push_back(u);
        }

        result.resize(n, -1);
        dfs(0, -1, 1, values);
        return result;
    }
};